The present invention according to a first aspect relates to a queue system for selection of storing positions in a memory for performing write operations on these from an online maintained idle list of addresses to free storing positions in the memory. The queue system also calculates addresses for collecting data earlier stored in the memory.
In accordance with second and third aspects the invention relates to a queue system for buffering data in a packet switch with a common buffer memory for one or more ports of the switch. The system uses a number of pointers identifying storing positions in the buffer memory. The pointers are moved between different logical lists for indicating the operation to be performed on the data in the buffer position pointed to.
The invention furthermore relates to methods for testing storing positions and pointers, respectively, in connection with queue systems of the kind indicated above.
When memories are used in computers and other equipment, address calculation decides the physical positions to be used for storing of a certain data. Most simply direct addressing, decision or calculations of which address to be used is performed at compiling of a program, or in connection with hardware design for devices having fixed programs. Indirect addressing and linked lists are examples of more flexible addressing methods. Here the address information is stored in other address positions or in counters, etc. The address calculation is thus not fixed but varies during execution for adaption to amount and format of the stored data.
Simple FIFO memories with direct addressing most often are realized with counters for incrementing write and read addresses, or in their most simple form are realized with fixed addresses in shift registers. In connection with dynamic indirect addressing address pointers are used, which are also stored in memories. At system start these pointers are initialized so as to obtain a valid set of pointers for the system to work with. The function of the system is then dependent on this pointer initialization being not corrupted during operation. Bit errors in a pointer value results in a lasting malfunction in the system. For systems being in continuous operation with high demands on reliability this is a problem.
Great semiconductor memories are traditionally equipped with redundance for improving the yield of the manufacture. By redundancy is here meant rows and columns of spare circuits, which may be connected into circuit to replace ordinary circuits. This is obtained by fusing fuses or by other means for permanently reconfiguring the circuit in the factory.
Testing is performed for determining circuits requiring reparation. If manufacturing errors occur and are such that they can be repaired by connection into circuit of spare circuits, the type of manufacturing error is determined and the repair is performed.
For semiconductor memories without redundancy, mapping between address and physical position in the memory is determined while designing the memory. For semiconductor memories with redundancy this mapping is partly set during the design and is completed during manufacture when erroneous memory positions shall be repaired.
In the case of disc memories a testing procedure is used before taking the disc into operation, during a formatting operation for determining the sections on the disc which may be used. The aim is to be able to use a disc with bad sections. The error hypothesis used is that certain positions on the disc may be bad due to the manufacture being not perfect. The dividing in good and bad sectors may be performed during the formatting process and is assumed not to need to be changed. The risk for disc addressing errors need not be taken into consideration during the formatting procedure.
In certain systems error correcting codes (ECC=Error Correcting Codes) are used for obtaining error tolerance against bit errors during operation. These errors occurring during operation may be soft or hard, i.e. temporary disturbances or fixed errors. The number of bits able to be corrected in each word is delimited. The code most often used may correct single bit errors and detect double bit errors. Quite recently it has been shown that a combination of error correcting codes and spare rows provides an error tolerance system which has a very high degree repairability of manufacturing errors in semiconductor memories, cf. IEEE transactions on computers, vol. 41 #9 September 1992, pp 1078-1087.
Repair of devices before they leave manufacture requires testing apparatus and equipment for fuse programming (a lasting change of connections in an electric circuit for influencing its function--also called fuse or antifuse), on the manufacturing line in the factory, and a manufacturing process including fuse components. This implies increased costs due to a prolongation of the manufacturing cycle. The degree of success with respect to the repair operations is limited by the fact that they are based on the use of spare rows and columns, and by the inflexibility with respect to the handling of sporadic single errors.
Use of error correcting codes takes care of isolated single errors. For full efficiency there is, however, required a combination with some sort of system with redundant rows. According to the state of the art this implies fuse programming and testing before the circuits leave the manufactory.
U.S. Pat. No. 4,049,956 provides an example of the state of the art as regards error detection during operation and describes supervision of a memory working in a time multiplexing mode. Incoming data words are stored temporarily in the respective steps of a multiple step memory and are read out for further revision. The testing is performed without taking the memory out of normal operation. The memory consists of a number of n steps which are periodically addressed in a repeated scanning cycle of n time slots in which binary words are written into and read out from the respective steps. Words written into a memory step are read out in the immediately following cycle. Malfunctions are detected by means of parity checks.
U.S. Pat. No. 3,863,227 describes the selection and testing of each one of individual electronic control elements used for accessing the different core elements in a core memory when the memory is on-line. There is thus the question of on-line test of a memory system, but not of the memory storing elements included in the memory. No use of parity tests is described.
U.S. Pat. No. 5,016,248 describes a queueing system for packet transfer without mentioning initialization or maintenance.